Graph

Graphs are used to represent series of relationships between a set of objects.

There are two main parts that make up a graph:

Nodes (a.k.a Vertices) are the objects of the graph. Each node usually contains a unique value.
Edges show how two nodes relate to each other. Edges can have different characteristics:
- Unweighted vs Weighted:
  - An unweighted edge simply shows a connection exists between two nodes.
    Example: Node A is connected to Node B.
  - A weighted edge shows a connection exists, and provides extra information like distance or cost of that connection.
    Example: Node A is connected to Node B with a distance of 50.
- Undirected (bidirected) vs Directed
  - An undirected edge represents a connection where you can travel in both directions.
    Example: You can go from Node A to Node B, and from Node B to Node A.
  - A directed edge represents a connection where you can only travel in one specified direction.
    Example: You can go from Node A to Node B, but NOT from Node B to Node A directly.

Examples of questions that we could use graphs to solve are:

What's the shortest distance between two nodes in a given weighted graph?
Is there a valid path to travel grom one specific node to another specific node in a given directed graph?
Does a certain value exist in a given graph?

Creating a graph

In Python, you can create a graph using an

adjacency matrix (2D array)
A matrix where each cell (i, j) indicates whether there's an edge from node i to node j.
```
matrix = [
[0, 1, 1],
[1, 0, 0],
[1, 0, 0],
]
```
In this simple graph, matrix[0][1] and matrix[1][0] are 1, which means there's an edge between node 0 and node 1. Also, matrix[0][2] and matrix[2][0] are 1, which means there's an edge between node 0 and node 2.
adjacency list (dictionary of lists)
A dictionary where each key is a node, and the value is a list of nodes that the node's connected to.
```
graph = [
0: [1, 2],
]
```
In this simple graph, there's an edge between node 0 and 1, and an edge between node 0 and 2.

Note

We recommend using adjacency lists since they're easier to understand and use. However, it's still worthwhile to familiarize yourself with adjacency matrices since some problems may provide an adjacency matrix graph to work with.

Examples of creating graphs

Unweighted Undirected Graph Example Unweighted Undirected Graph

Creating an unweighted undirected graph using an adjacency matrix:

num_nodes = 6 # number of nodes in the graph

edges = [(0, 1), (1, 2), (1, 4), (3, 4)]

# In one line:

# - [0] * num_nodes: Create an inner list with num_nodes elements, all set to 0.

# - [0] * num_nodes for _ in range(num_nodes): Create the inner list for num_nodes times.

# - [[0] * num_nodes for _ in range(num_nodes)]: Put the inner lists into an outer list.

# This creates a matrix of num_nodes x num_nodes where each cell has 0.

adj_matrix = [[0] * num_nodes for _ in range(num_nodes)]

# Populate the graph.

for edge in edges:

u, v = edge

adj_matrix[u][v] = 1

adj_matrix[v][u] = 1 # Only include for undirected graph

# Print the graph.

for row in adj_matrix:

print(row)

Creating an unweighted undirected graph using an adjacency list:

num_nodes = 6 # number of nodes in the graph

edges = [(0, 1), (1, 2), (1, 4), (3, 4)]

adj_list = defaultdict(list)

# Populate the graph.

for edge in edges:

u, v = edge

adj_list[u].append(v)

adj_list[v].append(u) # Only include for undirected graph

# Print the graph.

print(adj_list)

Unweighted Directed Graph Example Unweighted Directed Graph

Creating an unweighted directed graph using an adjacency matrix:

num_nodes = 6 # number of nodes in the graph

edges = [(0, 1), (1, 2), (3, 4), (4, 1)] # edges are directed (from, to)

# In one line:

# - [0] * num_nodes: Create an inner list with num_nodes elements, all set to 0.

# - [0] * num_nodes for _ in range(num_nodes): Create the inner list for num_nodes times.

# - [[0] * num_nodes for _ in range(num_nodes)]: Put the inner lists into an outer list.

# This creates a matrix of num_nodes x num_nodes where each cell has 0.

adj_matrix = [[0] * num_nodes for _ in range(num_nodes)]

# Populate the graph.

for edge in edges:

u, v = edge

adj_matrix[u][v] = 1

# Print the graph.

for row in adj_matrix:

print(row)

Creating an unweighted directed graph using an adjacency list:

num_nodes = 6 # number of nodes in the graph

edges = [(0, 1), (1, 2), (3, 4), (4, 1)] # edges are directed (from, to)

adj_list = defaultdict(list)

# Populate the graph.

for edge in edges:

u, v = edge

adj_list[u].append(v)

# Print the graph.

print(adj_list)

Weighted Directed Graph Example Weighted Directed Graph

Creating an weighted directed graph using an adjacency matrix:

num_nodes = 6 # number of nodes in the graph

edges = {

(0, 1): 5, # 0 -> 1 (weight 5)

(1, 2): 4, # 1 -> 2 (weight 4)

(3, 4): 6, # 3 -> 4 (weight 6)

(4, 1): 2 # 4 -> 1 (weight 2)

}

# In one line:

# - [0] * num_nodes: Create an inner list with num_nodes elements, all set to 0.

# - [0] * num_nodes for _ in range(num_nodes): Create the inner list for num_nodes times.

# - [[0] * num_nodes for _ in range(num_nodes)]: Put the inner lists into an outer list.

# This creates a matrix of num_nodes x num_nodes where each cell has 0.

adj_matrix = [[0] * num_nodes for _ in range(num_nodes)]

# Populate the graph.

# edges.items() returns [((0, 1), 5), ((1, 2), 4), ...]

for edge, weight in edges.items():

u, v = edge

adj_matrix[u][v] = weight

# Print the graph.

for row in adj_matrix:

print(row)

Creating an weighted directed graph using an adjacency list:

num_nodes = 6 # number of nodes in the graph

edges = {

(0, 1): 5, # 0 -> 1 (weight 5)

(1, 2): 4, # 1 -> 2 (weight 4)

(3, 4): 6, # 3 -> 4 (weight 6)

(4, 1): 2 # 4 -> 1 (weight 2)

}

adj_list = defaultdict(list)

# Populate the graph.

for edge, weight in edges.items():

u, v = edge

adj_list[u].append((v, weight))

# Print the graph.

print(adj_list)

Get the neighbors of a node in an adjacency matrix

O(n)

In an undirected graph, you need to traverse over either the column or row corresponding to the node.

In a directed graph, you traverse over the row (for outgoing edges) or column (for incoming edges).

# Get the neighbors of a node u in adjacency matrix.

def get_neighbors(adj_matrix, u):

neighbors = []

for v in range(len(adj_matrix)):

if adj_matrix[u][v] == 1:

neighbors.append(v)

return neighbors

adj_matrix = [

[0, 1, 0, 0, 0],

[1, 0, 1, 0, 1],

[0, 1, 0, 0, 0],

[0, 0, 0, 0, 1],

[0, 1, 0, 1, 0]

]

u = 1

print(f"The neighbors of {u} are: {get_neighbors(adj_matrix, u)}")

Getting neighboring nodes in an adjacency list

O(1)

The adjacency list stores all the neighbors of each key node, so we can just look up the node in the dictionary and return its value.

# Get the neighbors of a node u in adjacency list.

def get_neighbors(adj_matrix, u):

if u in adj_list:

return adj_list[u]

return []

adj_list = {

0: [1],

1: [0, 2, 4],

2: [1],

4: [1, 3],

3: [4]

}

u = 1

print(f"The neighbors of {u} are: {get_neighbors(adj_list, u)}")

PrevTree

NextHeap

InterviewCrunch

Graph

Creating a graph

adjacency matrix (2D array)

adjacency list (dictionary of lists)

Note

Examples of creating graphs

Get the neighbors of a node in an adjacency matrix

Getting neighboring nodes in an adjacency list